//二叉树类
class TreeNode {
    val; //节点值
    left; //左子节点
    right; //右子节点
    //构造函数
    constructor(val, left = null, right = null) {
        this.val = val; //节点值
        this.left = left; //左子节点
        this.right = right; //右子节点
    }
}


let TreeNode1 = new TreeNode(1);
let TreeNode2 = new TreeNode(2);
let TreeNode3 = new TreeNode(3);
let TreeNode4 = new TreeNode(4);
let TreeNode5 = new TreeNode(5);
let TreeNode6 = new TreeNode(6);
let TreeNode7 = new TreeNode(7);
let TreeNode8 = new TreeNode(8);
let TreeNode9 = new TreeNode(9);

//构建二叉树
TreeNode1.left = TreeNode2;
TreeNode1.right = TreeNode3;
TreeNode2.left = TreeNode4;
// TreeNode2.right = TreeNode5;
TreeNode3.left = TreeNode6;
TreeNode3.right = TreeNode7;
// TreeNode4.left = TreeNode8;
TreeNode4.right = TreeNode9;

/**
 * 
 *       1
 *      / \
 *     2   3
 *    /   / \
 *   4   6  7
 *    \
 *     9
 * 
 */

//层序遍历转换成数组的实现
function levelOrder(root){ //传入根节点
    //创建一个队列用于存储节点,根节点入队
    const queue = [root];
     // 初始化一个列表，用于保存遍历序列
    const list = [];
    while(queue.length){ //队列不为空
        let node = queue.shift(); //队首元素出队,将队首元素赋值给node
        if(node){
            list.push(node.val); //将节点值添加到列表中
            queue.push(node.left); //将左子节点入队
            queue.push(node.right); //将右子节点入队
        }else{ //如果节点为空,则添加null到列表中
            list.push(null); //添加null到列表中
        }
    }

    while(list.length && list[list.length - 1] === null){
        list.pop(); //如果两个都是null的话,弹出最后一项
    }
    return list; //返回遍历序列
}
console.log(levelOrder(TreeNode1)); //打印层序遍历结果